/**
 * File: LocalSearch.h
 *
 * Integrantes:
 * @author Jormar Arellano   (05-37840) <jormar.arellano@gmail.com>
 * @author Sabrina Fernández (05-38163) <sabrinamfm@gmail.com>
 */

#ifndef LOCALSEARCH_H
#define	LOCALSEARCH_H

#include "graph.h"

#ifdef	__cplusplus
extern "C" {
#endif

/**
 * Un vecino del grafo, formado por algun cambio de color en algun(os) vertice(s).
 *
 * Un vecino es un grafo con una pequena modificacion del original. Un GraphNeighbor contiene 
 * la informacion necesaria para realizar los cambios en el grafo original y generar el vecino
 * deseado; de esta forma, se evita tener que generar el grafo como tal, y solo se espera a 
 * que sea necesario.
 */
typedef struct {
    Graph *graph;		// Grafo original.
	ArrayList *changes; //Lista de cambios. (ArrayList(Vertex *))
} GraphNeighbor;

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Parametros globales del metodo
 * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/** 
 * Numero de iteraciones que realiza Local Search.
 */
long ls_iter;

/** 
 * Activa el modo verbose.
 */
int ls_verbose;

/** 
 * Criterio de aceptacion usara Local Search.
 */
int (*ls_acceptance)(GraphNeighbor *, int *);

/** 
 * Obtiene un vecino para el grafo dado.
 */
GraphNeighbor *(*ls_getNeighbor)(Graph *graph);

/** 
 * Inicializa las variables globales de Local Search.
 */
void ls_defaults();

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Funciones para manipular un GraphNeighbor
 * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**
 * Crea un vecino del grafo reservando memoria.
 * @param   graph   El grafo al cual se le va a buscar un vecino.
 * @return  Un nuevo vecino del grafo.
 */
GraphNeighbor *newGraphNeighbor(Graph *graph);

/**
 * Crea un respaldo de los cambios que se necesitan para crear un vecino, 
 * tal que se pueda obtener el grafo original si hace falta.
 * @param	gn	Vecino al cual se le hara un respaldo.
 */
GraphNeighbor *createReverseNeighbor(GraphNeighbor *gn);

/**
 * Libera los recursos usados por un GraphNeighbor.
 * @param	gn	Vecino al cual se le liberaran los recursos.
 */
void freeGraphNeighbor(GraphNeighbor *gn);

/**
 * Realiza los cambios especificados en el GraphNeighbor al grafo original.
 * @param   gn	Vecino al cual se le realizaran los cambios.
 * @return  El puntero al grafo donde se realizaron los cambios.
 */
Graph *realizeChanges(GraphNeighbor *gn);

/**
 * Crea un grafo nuevo en base a los cambios especificados
 * @param   gn	Vecino al cual se le van a realizar los cambios.
 */
Graph *newGraphFromChanges(GraphNeighbor *gn);

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Funciones de vecindario
 * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**
 * Vecindario one-exchange. Consiste en cambiar el color de un nodo de forma aleatoria.
 * @param   graph	Grafo al que se le buscara el vecindario por un cambio.
 * @return  Un nuevo grafo vecino con los cambios.
 */
GraphNeighbor *getNeighbor_oneExchange(Graph *graph);

/**
 * Un vertice en conflicto es escogido al azar para colocarle un color que genere el menor numero de conflictos.
 * @param   graph	Grafo al que se le van a analizar los conflictos.
 * @return  Un nuevo grafo vecino con los cambios.
 */
GraphNeighbor *getNeighbor_minConflicts(Graph *graph);

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Criterios de aceptacion
 * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**
 * Evalua la calidad de un vecino en base a si es factible o no.
 * @param   gn      Grafo vecino con los cambios que lo definen.
 * @param   count   Referencia al contador de iteraciones.
 * @return  TRUE si la solucion se acepta
 *			FALSE si la solucion no se acepta.
 */
int ls_acceptance_isFactible(GraphNeighbor *gn, int *count);

/**
 * Evalua si mejora la coloracion del grafo con ese cambio. Cambiara el contador de ser necesario.
 * @param   gn      Grafo vecino con los Cambios que lo definen.
 * @param   count   Referencia al contador de iteraciones.
 * @return  TRUE si la solucion se acepta.
 *			FALSE si la solucion no se acepta.
 */
int ls_acceptance_bestColor(GraphNeighbor *gn, int *count);

/**
 * Se queda con la solucion que minimice el numero de conflictos.
 * @param   gn      Cambios que definen al vecino.
 * @param   count   Referencia al contador de iteraciones.
 * @return  TRUE si la solucion se acepta.
 *			FALSE si la solucion no se acepta.
 */
int ls_acceptance_minConflicts(GraphNeighbor *gn, int *count);

/**
 * Evalua ls_acceptance_isFactible. Adicionalmente, si return es TRUE, 
 * ejecuta ls_acceptance_bestColor para reiniciar el contador.
 *
 * @param   gn      Cambios que definen al vecino.
 * @param   count   Referencia al contador de iteraciones.
 * @return  TRUE si la solucion se acepta.
 *			FALSE si la solucion no se acepta.
 */
int ls_acceptance1(GraphNeighbor *gn, int *count);

/**
 * Evalua una solucion en base a penalidades.
 * La formula general usada es: sum(2*Ci*Ei) - sum( Ci^2 )
 * @param	gn		Cambios que definen al vecino.
 * @param	count	Referencia al contador de iteraciones.
 * @return	Un entero que significa la penalidad.
 */
int ls_acceptance_penaltyFunction(GraphNeighbor *gn, int *count);

/**
 * Algoritmo principal de busqueda local. Esta funcion ejecuta la busqueda 
 * de una solucion inicial, y luego llama a apply_local_search para 
 * realizar la busqueda local.
 * @param   graph     Grafo al que se aplicara el algoritmo.
 * @return  El grafo resultante de aplicar la busqueda.
 */
Graph *local_search(Graph *graph);

/**
 * Ciclo principal de la busqueda local. Se asume que ya se ha encontrado una solucion inicial.
 * @param   graph   Solucion que se desea mejorar.
 * @return  El grafo mejorado.
 */
Graph *apply_local_search(Graph *graph);

#ifdef	__cplusplus
}
#endif

#endif

